Otimização Convexa: Condições de Otimalidade para Restrições de Igualdade

Imagine um sistema físico, como uma corrente pendurada, buscando seu estado de menor energia. Se as extremidades estão fixas, o sistema não pode se mover livremente. A otimalidade é alcançada quando as forças internas (o gradiente da energia potencial) são perfeitamente equilibradas pelas forças de tensão exercidas pelas restrições. Na otimização convexa, esse equilíbrio é capturado pelas condições de KKT para restrições de igualdade.

A Geometria da Viabilidade

Para um problema convexo com restrições de igualdade $Ax = b$, um vetor $v \in \mathbf{R}^n$ é um direção viável se $Av = 0$. Isso significa que mover-se na direção $v$ mantém a restrição: $A(x + v) = b$ se $Ax = b$.

Para que $x^*$ seja ótimo, a derivada direcional $\nabla f(x^*)^T v$ deve ser zero para todas as direções viáveis $v$ no núcleo $\mathcal{N}(A)$. Isso implica que o gradiente $\nabla f(x^*)$ deve ser ortogonal a $\mathcal{N}(A)$, levando à existência dos multiplicadores de Lagrange.

A Condição de Otimalidade

Um ponto $x^*$ é ótimo se e somente se existe um vetor $\nu^* \in \mathbb{R}^p$ tal que:

$\nabla f(x^*) + A^T \nu^* = 0$

Isso forma um sistema de equações lineares que caracteriza o equilíbrio entre a descida do objetivo e a variedade das restrições.

O Gradiente Projetado

A projeção euclidiana do gradiente negativo $-\nabla f(x)$ sobre o núcleo $\mathcal{N}(A)$ é dada por:

$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$

Este vetor representa a "melhor" direção descendente viável. Crucialmente, $x$ é ótimo se e somente se $\Delta x_{\text{pg}} = 0$.

O Sistema de KKT e as Propriedades da Matriz

Podemos resolver simultaneamente o passo de Newton e as variáveis duais usando o sistema de blocos:

$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$

Observação sobre as Propriedades Espectrais da Matriz: A matriz de KKT é simétrica mas indeterminada. Se a matriz for não singular, ela possui exatamente $n$ autovalores positivos e $p$ autovalores negativos. Isso implica que o ponto ótimo $(x^*, \nu^*)$ é um ponto de sela da Lagrangiana $L(x, \nu) = f(x) + \nu^T(Ax-b)$, e não um mínimo local simples no espaço combinado primal-dual.

🎯 Princípio Central

A otimalidade em problemas com restrições de igualdade exige que o gradiente seja ortogonal ao núcleo da restrição. Isso nos permite interpretar o passo de Newton como a solução de uma aproximação linear das condições de KKT.

PERGUNTA 1

O que define uma 'direção viável' $v$ em um ponto $x$ para a restrição $Ax = b$?

$Av = b$

$Av = 0$

$\|v\|_2 = 1$

$A^T v = 0$

PERGUNTA 2

Qual é a interpretação física da condição $\nabla f(x^*) + A^T \nu^* = 0$?

O gradiente é zero em todas as direções.

A função objetivo alcançou um mínimo global sem restrições.

A força interna (gradiente) é equilibrada pela 'tensão' proveniente das restrições.

Os multiplicadores de Lagrange devem ser todos positivos.

PERGUNTA 3

Se a matriz de KKT for não singular, qual é sua assinatura de autovalores?

Todos os $n+p$ autovalores são positivos.

$n$ autovalores positivos e $p$ autovalores negativos.

$p$ autovalores positivos e $n$ autovalores negativos.

Todos os autovalores são reais e não nulos, mas os sinais dependem de $f(x)$.

PERGUNTA 4

O gradiente projetado $\Delta x_{\text{pg}}$ é zero se e somente se:

O gradiente $\nabla f(x)$ é zero.

O ponto $x$ está no núcleo de $A$.

O ponto $x$ satisfaz as condições de otimalidade de primeira ordem.

A matriz $A$ é quadrada e invertível.

PERGUNTA 5

No sistema $\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$, o que representa $v$?

A solução ótima $x^*$.

O vetor dos multiplicadores de Lagrange.

O gradiente projetado $\Delta x_{\text{pg}}$.

O resíduo primal $Ax - b$.